
#pragma once
#include <iostream>
#include <assert.h>
#include "QueueAbs.h"

using namespace std;

template<class Type>
class QueueArray :public QueueAbs<Type>
{
public:
	const QueueArray<Type>& operator=(const QueueArray<Type>&);
	bool isEmpty()const;
	bool isFull()const;
	void initializeQueue();
	Type front()const;
	Type back()const;
	int queueLen()const;
	void addElem(const Type&);
	void deleteElem();
	QueueArray(int size = 100);  //设置默认最大数组长度
	QueueArray(const QueueArray<Type>&);
	~QueueArray();
	void printQueue()const;
private:
	int maxSize;
	int head;
	int tail;
	Type* headPtr;
};


template<class Type>
bool QueueArray<Type>::isEmpty()const
{
	return tail == head;
}

template<class Type>
bool QueueArray<Type>::isFull()const
{
	return (tail+1)%maxSize == head;
}

template<class Type>
void QueueArray<Type>::initializeQueue()
{
	head = 0;
	tail = 0;
}

template<class Type>
Type QueueArray<Type>::front()const
{
	assert(!isEmpty());
	return headPtr[head];
}

template<class Type>
Type QueueArray<Type>::back()const
{
	assert(!isEmpty());
	return headPtr[(tail-1+maxSize)%maxSize];
}

template<class Type>
int QueueArray<Type>::queueLen()const
{
	return (tail - head + maxSize) % maxSize;
}

template<class Type>
void QueueArray<Type>::addElem(const Type& elem)
{
	if (!isFull())
	{
		headPtr[tail] = elem;
		tail = (tail + 1) % maxSize;
	}
	else
		cout << "The queue is full,can not add an element in it" << endl;
}

template<class Type>
void QueueArray<Type>::deleteElem()
{
	if (!isEmpty())
		head = (head + 1) % maxSize;
	else
		cout << "can not remove an element from the queue" << endl;
}

template<class Type>
QueueArray<Type>::QueueArray(int size)
{
	if (size <= 0)
	{
		cout << "Size of the array to hold the queue must "
			<< "be positive." << endl;
		cout << "Creating an array of size 100." << endl;
		maxSize = 100;
		headPtr = new Type[maxSize];
		assert(headPtr != nullptr);
	}
	else
	{
		maxSize = size;
		head = 0;
		tail = 0;
		headPtr = new Type[maxSize];
		assert(headPtr != nullptr); //记得判断内存是否分配成功
	}
}

template<class Type>
QueueArray<Type>::QueueArray(const QueueArray<Type>& otherQueue)
{
	head = otherQueue.head;
	tail = otherQueue.tail;
	maxSize = otherQueue.maxSize;
	headPtr = new Type[maxSize];
	assert(headPtr != nullptr);
	for (int i = 0; i < otherQueue.queueLen(); i++)
		headPtr[(head + i) % maxSize] = otherQueue.headPtr[(head + i) % maxSize];
}

template<class Type>
QueueArray<Type>::~QueueArray()
{
	delete[]headPtr;
}

template<class Type>
const QueueArray<Type>& QueueArray<Type>::operator=(const QueueArray<Type>& otherQueue)
{
	if (this != &otherQueue)
	{
		head = otherQueue.head;
		tail = otherQueue.tail;
		if (maxSize != otherQueue.maxSize)
		{
			delete[]headPtr;
			headPtr = new Type[otherQueue.maxSize];
			assert(headPtr != nullptr);
		}
		maxSize = otherQueue.maxSize;
		if (!otherQueue.isEmpty())
		{
			for (int i = 0; i < otherQueue.queueLen(); i++)
				headPtr[(head+i)%maxSize] = otherQueue.headPtr[(head + i) % maxSize];  //神来之笔，不然因为空了一个元素，而且元素位置不确定，一旦赋值就会出现问题
		}
	}
	else
	{
		cout << "cannot self assignment" << endl;
	}
	return *this;
}

template<class Type>
void QueueArray<Type>::printQueue()const
{
	if (!isEmpty())
	{
		cout << "The queue:";
		for (int i = 0; i < queueLen(); i++)
		{
			cout << headPtr[(head + i) % maxSize] << " ";
		}
		cout << endl;
	}
}
